#include <linux/sched.h>
#include <linux/kernel.h>
#include <asm/system.h>

extern int _end;
struct buffer_head *start_buffer = (struct buffer_head *) &_end;
struct buffer_head *hash_table[NR_HASH];
static struct buffer_head *free_list;
static struct task_struct *buffer_wait = NULL;
int NR_BUFFERS = 0;

static inline void wait_on_buffer(struct buffer_head *bh)
{
    cli();
    while (bh->b_lock)
        sleep_on(&bh->b_wait);
    sti();
}

void invalidate_buffers(int dev)
{
    int i;
    struct buffer_head *bh;

    bh = start_buffer;
    for (i = 0; i < NR_BUFFERS; i++, bh++) {
        if (bh->b_dev != dev)
            continue;
        if (bh->b_dev == dev)   // 如果是指定的设备
            bh->b_uptodate = bh->b_dirt = 0;
    }
}

void check_disk_change(int dev)
{
    if (MAJOR(dev) != 2)
        return;
    if (!floppy_change(dev & 0x03))
        return;
    invalidate_buffers(dev);
}

#define _hashfn(dev, block) (((unsigned)(dev ^ block)) % NR_HASH)
#define hash(dev, block) hash_table[_hashfn(dev, block)]

static inline void remove_from_queues(struct buffer_head *bh)
{
    // 将bh移出哈希链表
    if (bh->b_next)
        bh->b_next->b_prev = bh->b_prev;
    if (bh->b_prev)
        bh->b_prev->b_next = bh->b_next;
    if (hash(bh->b_dev, bh->b_blocknr) == bh)
        hash(bh->b_dev, bh->b_blocknr) = bh->b_next;

    if (!(bh->b_prev_free) || !(bh->b_next_free))
        panic("Free block list corrupted");
    // 将bh移出free_list循环链表
    bh->b_prev_free->b_next_free = bh->b_next_free;
    bh->b_next_free->b_prev_free = bh->b_prev_free;
    if (free_list == bh)
        free_list = bh->b_next_free;
}

static inline void insert_into_queues(struct buffer_head *bh)
{
    // 将bh加入到free_list循环链表的末尾（free_list为头节点）
    bh->b_next_free = free_list;
    bh->b_prev_free = free_list->b_prev_free;
    free_list->b_prev_free->b_next_free = bh;
    free_list->b_prev_free = bh;

    bh->b_prev = NULL;
    bh->b_next = NULL;
    // 在执行该函数前会设置b_dev的值，如果为0，说明这个设备不可用
    if (!bh->b_dev)
        return;
    // 将bh加入到哈希链表
    bh->b_next = hash(bh->b_dev, bh->b_blocknr);
    hash(bh->b_dev, bh->b_blocknr) = bh;
    if (bh->b_next)
        bh->b_next->b_prev = bh;
}

static struct buffer_head *find_buffer(int dev, int block)
{        
    struct buffer_head *tmp;

    for (tmp = hash(dev, block); tmp != NULL; tmp = tmp->b_next)
        if (tmp->b_dev == dev && tmp->b_blocknr == block)   // 对比链表中的元素
            return tmp;
    return NULL;
}

struct buffer_head *get_hash_table(int dev, int block)
{
    struct buffer_head *bh;

    while (1) {
        bh = find_buffer(dev, block);
        if (!bh)    // 逻辑块还没被读过
            return NULL;
        bh->b_count++;
        wait_on_buffer(bh); // 如果正在读取数据，需要等待
        if (bh->b_dev == dev && bh->b_blocknr == block)
            return bh;
        bh->b_count--;
    }
}

struct buffer_head *getblk(int dev, int block)
{
    struct buffer_head *bh;

repeat:
    bh = get_hash_table(dev, block);
    if (bh)
        return bh;
    for (bh = free_list->b_next_free; bh != free_list; bh = bh->b_next_free) {
        if (bh->b_count)
            continue;
        break;
    }
    if (!bh) {  // 如果没有可用的缓冲头结构体
        sleep_on(&buffer_wait);
        goto repeat;
    }
    bh->b_count = 1;    // 读取一个逻辑块
    bh->b_dirt = 0;     // 数据还未被修改
    bh->b_uptodate = 0; // 还未加载数据
    remove_from_queues(bh); // 从链表中移除
    bh->b_dev = dev;
    bh->b_blocknr = block;
    insert_into_queues(bh); // 插入到链表末尾
    return bh;
}

void brelse(struct buffer_head *buf)
{
    if (!buf)
        return;
    wait_on_buffer(buf);
    if (!(buf->b_count--))
        panic("Trying to free free buffer");
    wake_up(&buffer_wait);
}

struct buffer_head *bread(int dev, int block)
{
    struct buffer_head *bh;
    bh = getblk(dev, block);
    if (!bh)
        panic("bread: getblk returned NULL\n");
    if (bh->b_uptodate)
        return bh;
    ll_rw_block(READ, bh);
    wait_on_buffer(bh);
    if (bh->b_uptodate)
        return bh;
    
    brelse(bh);
    return NULL;
}

void buffer_init(long buffer_end)
{
    struct buffer_head *h = start_buffer;
    void *b;
    int i;

    if (buffer_end == 1 << 20)
        b = (void *) (640 * 1024);
    else
        b = (void *) buffer_end;
    while ((b -= BLOCK_SIZE) >= ((void *) (h + 1))) {
        h->b_dev = 0;
        h->b_dirt = 0;
        h->b_count = 0;
        h->b_lock = 0;
        h->b_uptodate = 0;
        h->b_wait = NULL;
        h->b_next = NULL;
        h->b_prev = NULL;
        h->b_data = (char *) b;
        h->b_prev_free = h - 1;
        h->b_next_free = h + 1;
        h++;
        NR_BUFFERS++;
        if (b == (void *) 0x100000) // 0xA0000-0x100000是显存和BIOS ROM
            b = (void *) 0xA0000;   // 跳过这一段
    }
    h--;
    free_list = start_buffer;
    free_list->b_prev_free = h;
    h->b_next_free = free_list;
    for (i = 0; i < NR_HASH; i++)
        hash_table[i] = NULL;
}